package arithmetic.bigFileSort;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Random;

import org.junit.Test;

/**
 * 假如有1T大文件数据，每行一个数据是乱序的，内存最大只有1G，实现一个算法将这个大文件的数据都排序
 *
 * @author lidd
 *
 */
public class BigFileSort {

	public static void main(String[] args) throws IOException {


		// 我们模拟一个1T大文件的数据，这里模拟不到1T，我们可以给这个文件输入百万千万条甚至上亿条数据来假设这就是1T大数据，
		// 这个数据放到F盘的sort目录下，这里需要在F盘新建一个sort的文件夹
		String filePath = "F:\\sort";

		// 切分文件的路径，这个路径放将大文件切分后的小文件，需要在刚刚新建的sort目录下新建一个split文件夹
		String sqlitFilePath = "F:\\sort\\split";

		// 数据的个数，这里的个数就是我们说的很多个数，为了快速能见到效果先设小一点，要不然会很慢等半天
		int countNumbers = 100000;

		// 这个是我们要切分的文件的个数，1T数据按1G内存来分是要切分成1024个文件的，这里我们就切分成10个
		int fileCount = 10;

		// 每次排序的个数，这个数我们可以调，现在共有10个文件，每次读取每个文件的一行放入列表中的话一共才10个数据，
		//每10个数据排序一次似乎有些不必要，所以我们可以利用list.size和这个值得取余值来控制当list里有多少数据时给他排一次序
		//比如现在这个数值是300，我们的list.size的值取余它等于0的话就给他排序一次，那么就是相当于list没有300个数时排序一次
		int countAccuracy = 1 * fileCount;

		/*
		// 将我们模拟的随机数据写入大数据文件中
		createBigDataFile(filePath, countNumbers);
		System.out.println("存储完毕");
		//存储完数据后，我们给大文件数据排序进行计时
		long startNumber = System.currentTimeMillis();
		// 将大数据文件切分到十个小文件中
		sqlitFileDate(filePath, sqlitFilePath, fileCount);
		System.out.println("文件切割完毕！");

		// 把每个文件的数据先进行排序一遍，使他们都成为有序的文件
		singleFileDataSort(sqlitFilePath, fileCount);
		System.out.println("每个切割文件排序完毕！");

		*/
		// 十个文件数据读取行进行比较并写入到目标文件中
		splidFileRowSort(filePath, sqlitFilePath, countAccuracy, fileCount);
		System.out.println("大文件排序完毕");
		long stopNumber = System.currentTimeMillis();
		//System.out.println("耗时" + (stopNumber - startNumber) / 1000 + "秒");
	}

	/**
	 * 写入大数据文件,模拟创造一个大数据文件，里面有很多条数据
	 * @param path
	 * @param CountNumbers
	 * @throws IOException
	 */
	public static void createBigDataFile(String path, int CountNumbers) throws IOException {
		// 大数据文件在F:\\sort\\source.txt
		path = path + "\\source.txt";
		FileWriter fileWriter = new FileWriter(path);
		BufferedWriter bufferedWriter = new BufferedWriter(fileWriter);
		for (int i = 0; i < CountNumbers; i++) {
			bufferedWriter.write(new Random().nextInt(Integer.MAX_VALUE) + "\r\n");
		}
		bufferedWriter.flush();
		bufferedWriter.close();

	}

	/**
	 * 将大数据文件切分到另外的十个小文件中
	 * @param filepath
	 * @param splitFilePath
	 * @param CountFile
	 * @throws IOException
	 */
	public static void sqlitFileDate(String filepath, String splitFilePath, int CountFile) throws IOException {
		FileWriter fileWriter = null;
		BufferedWriter bufferedWriter = null;
		//读取源文件，也就是我们模拟的未排序的大数据文件
		FileReader fileReader = new FileReader(filepath + "\\source.txt");

		// filereader后面还可以加参数，如缓存大小可设置new BufferedReader(fileReader，20 * 1024 * 1024);
		// 当我们不知道1T有多少数据时应该用这个来限制读取到内存的数据的吧，要不然内存放不下
		BufferedReader bufferedReader = new BufferedReader(fileReader);

		// 初始化文件流对象集合,用来创建分割文件
		LinkedList<FileWriter> fileWriterList = new LinkedList<FileWriter>();
		LinkedList<BufferedWriter> bufferedWriterList = new LinkedList<BufferedWriter>();
		for (int j = 1; j <= CountFile; j++) {

			// 声明对象，这里创建一个一个的分割文件，名为temp1.txt，temp2.txt...temp10.txt
			fileWriter = new FileWriter(splitFilePath + "\\temp" + j + ".txt", false);
			bufferedWriter = new BufferedWriter(fileWriter);

			// 将声明的对象装入集合
			fileWriterList.add(fileWriter);
			bufferedWriterList.add(bufferedWriter);
		}
		// 判断是文件流中是否还有数据返回,这方法的意思是如果文件流中还有数据，他的值就为true，流中没数据了它的值变为false
		int i = 1;
		while (bufferedReader.ready()) {

			int count = 1;// 初始化第一文件流
			for (BufferedWriter bw : bufferedWriterList) {
				BufferedWriter type = bw;
				if (i == count)// 判断轮到第几个文件流写入数据了
				{
					// 写入数据，跳出，进行下一个文件流，下一个数据的写入
					type.write(bufferedReader.readLine() + "\r\n");
					break;
				}
				count++;
			}
			// 判断是否到了最后一个文件流了
			if (i >= CountFile) {
				i = 1;
			} else {
				i++;
			}
		}
		bufferedReader.close();
		for (BufferedWriter obj : bufferedWriterList) {
			BufferedWriter object = obj;
			object.flush();
			object.close();
		}
	}

	/**
	 * 把每个文件的数据进行排序，排好序后再将它写入文件，使每个单个文件的数据都变成有序的
	 * @param splidFilePath
	 * @param fileCount
	 * @throws IOException
	 */
	public static void singleFileDataSort(String splidFilePath, int fileCount) throws IOException {
		ArrayList<Integer> numbers = null;
		for (int i = 1; i <= fileCount; i++) {
			numbers = new ArrayList<Integer>();
			String path = splidFilePath + "\\temp" + i + ".txt";
			try {
				FileReader fileReader = new FileReader(path);
				BufferedReader bufferedReader = new BufferedReader(fileReader);
				while (bufferedReader.ready()) {
					// 将读取的单个数据加入到集合里面
					numbers.add(Integer.parseInt(bufferedReader.readLine()));
				}
				// 对集合内的数据进行排序
				Integer[] arr = numbers.toArray(new Integer[numbers.size()]);
				//将每个文件的数据利用快速排序排一遍，使他变成有序的，因为切分时每个文件的大小总不超过内存大小所以是可以排序的
				quickSort(arr,0,arr.length-1);
				// 将排序好的数据写入源文件
				orderNumsToFile(arr, path);
				//关闭流
				bufferedReader.close();
			} catch (NumberFormatException e) {
				e.printStackTrace();
			} catch (FileNotFoundException e) {
				e.printStackTrace();
			} catch (IOException e) {
				e.printStackTrace();
			}
		}
	}

	/**
	 * 快速排序算法，用来排序单个文件的数据，单个文件数据大小不超过内存大小
	 * @param arr
	 * @param _left
	 * @param _right
	 */
	public static void quickSort(Integer arr[],int _left,int _right){
		int left = _left;
		int right = _right;
		int temp = 0;
		if(left <= right){   //待排序的元素至少有两个的情况
			temp = arr[left];  //待排序的第一个元素作为基准元素
			while(left != right){   //从左右两边交替扫描，直到left = right

				while(right > left && arr[right] >= temp)
					right --;        //从右往左扫描，找到第一个比基准元素小的元素
				arr[left] = arr[right];  //找到这种元素arr[right]后与arr[left]交换

				while(left < right && arr[left] <= temp)
					left ++;         //从左往右扫描，找到第一个比基准元素大的元素
				arr[right] = arr[left];  //找到这种元素arr[left]后，与arr[right]交换

			}
			arr[right] = temp;    //基准元素归位
			quickSort(arr,_left,left-1);  //对基准元素左边的元素进行递归排序
			quickSort(arr, right+1,_right);  //对基准元素右边的进行递归排序
		}
	}

	/**
	 * 对每个文件排好序的数据重新放到文件中，此时，每个文件的数据都是有序的
	 * @param arr
	 * @param splidFilePath
	 */
	public static void orderNumsToFile(Integer[] arr, String splidFilePath) {
		try {
			FileWriter fileWriter = new FileWriter(splidFilePath);
			BufferedWriter bufferedWriter = new BufferedWriter(fileWriter);
			for (Integer obj : arr) {
				Object object = obj;
				bufferedWriter.write(object + "\r\n");
			}
			bufferedWriter.flush();
			bufferedWriter.close();
		} catch (IOException e) {
			e.printStackTrace();
		}
	}

	/**
	 * 所有切割文件数据排序最终写入到目标总文件中
	 * @param filepath
	 * @param splitFilePath
	 * @param countAccuracy
	 * @param fileCount
	 * @throws IOException
	 */
	@Test
	public static void splidFileRowSort(String filepath, String splitFilePath, int countAccuracy, int fileCount)
			throws IOException {
		LinkedList<Integer> numbers = new LinkedList<Integer>(); // 添加数据，进行排序
		Integer temp = null; // 记录每次排序剩下的最后一个数字
		boolean ispass = false;
		LinkedList<String> ispasses = null; // 记录数据文件的状态信息
		FileWriter fileWriter = new FileWriter(filepath + "\\SortOver.txt", false); // 创建文件流，以便整合的数据写入
		BufferedWriter bufferedWriter = new BufferedWriter(fileWriter);
		FileReader fileReader = null; // 声明读取文件流
		BufferedReader bufferedReader = null; // 声明BufferedReader
		LinkedList<BufferedReader> bufferedReaderList = new LinkedList<BufferedReader>(); // 初始化文件流对象集合
		LinkedList<FileReader> fileReaderList = new LinkedList<FileReader>();
		for (int j = 1; j <= fileCount; j++) {

			// 开启所有子文件流访问所有子文件的数据
			fileReader = new FileReader(splitFilePath + "\\temp" + j + ".txt");

			// 开启所有BufferedReader，方便下次的整行的读取
			bufferedReader = new BufferedReader(fileReader);

			// 将所有 FileReader对象装入集合
			fileReaderList.add(fileReader);

			// 将所有 BufferedReader对象装入集合
			bufferedReaderList.add(bufferedReader);
		}

		for (;;) {

			// 将十个切割文件 是否有数据情况 存入集合，以方便后面做判断
			ispasses = new LinkedList<String>();

			// 分别读取十个源文件的每行每行的数据
			for (BufferedReader obj : bufferedReaderList) {
				BufferedReader object = obj;
				//如果文件流中还有数据，他的值就为true，流中没数据了它的值变为false
				while (object.ready()) {
					// 添加所有文件流的每次读取一行的数据
					numbers.add(Integer.parseInt(object.readLine().toString()));
					break;
				}
				if (object.ready() == false)
					ispasses.add("true"); // 将各文件中的数据状态存入集合中
			}

			// 在这里处理list的数据是否够一次排序的标准，若等于300个数就让他排序一次，若不等于就继续让他添加数
			if (numbers.size() % countAccuracy == 0 && ispass == false) {

				Integer[] arr = numbers.toArray(new Integer[numbers.size()]);
				//利用快速排序将list中的数据排序
				quickSort(arr,0,arr.length-1);

				// 接收最大的数据，其它的数据写入总排序文件
				temp = orderDataToDestFile(arr, false, countAccuracy, bufferedWriter);

				// 分别读取十个源文件的每行每行的数据
				for (BufferedReader obj : bufferedReaderList) {
					BufferedReader object = obj;
					//如果文件流中还有数据，他的值就为true，流中没数据了它的值变为false
					while (object.ready()) {
						// 添加所有文件流的每次读取一行的数据
						if(temp == Integer.parseInt(object.readLine().toString())) {
							//思路，通过这个数所在的bufferedReader得到他所在的file，然后删除此file的第一行，也就是这个数字
							//删除后第二行的会顶上来成为第一行，然后再去遍历每个文件的第一行进行排序，再把最小的放到目标总文件中
							break;
						}else {
							continue;
						}
					}
					if (object.ready() == false)
						ispasses.add("true"); // 将各文件中的数据状态存入集合中
				}


				// 清空已排序数据，重新初始化集合，再次接受别的未排序数据
				numbers = new LinkedList<Integer>();

				// 添加上一组比较剩下的数据
				numbers.add(temp);
				ispass = true;

				continue;
			}
			//
			if (ispass) {
				if (numbers.size() % countAccuracy == 1 && numbers.size() > 1) {
					Integer[] arr = numbers.toArray(new Integer[numbers.size()]);
					//将每个文件的数据利用快速排序排一遍，使他变成有序的，因为切分时每个文件的大小总不超过内存大小所以是可以排序的
					quickSort(arr,0,arr.length-1);

					// 轮训接收接收最大的数，将它写入总文件
					temp = orderDataToDestFile(arr, true, countAccuracy, bufferedWriter);
					numbers = new LinkedList<Integer>();
					numbers.add(temp);
					continue;
				}
			}

			// 判断是不是十个文件都没有数据，若都没有数据，说明10个文件数据都读取完毕，
			if (ispasses.size() == fileCount) {
				Integer[] arr = numbers.toArray(new Integer[numbers.size()]);
				//将每个文件的数据利用快速排序排一遍，使他变成有序的，因为切分时每个文件的大小总不超过内存大小所以是可以排序的
				quickSort(arr,0,arr.length-1);
				temp = orderDataToDestFile(arr, true, countAccuracy, bufferedWriter);
				numbers = new LinkedList<Integer>();
				break;
			}
		}
		// 关闭写入流
		bufferedWriter.flush();
		bufferedWriter.close();

		// 关闭所有的BufferedReader
		for (BufferedReader obj : bufferedReaderList) {
			BufferedReader object = obj;
			object.close();
		}

	}

	/**
	 * 对数据进行排序,写入最终文件中
	 * @param list
	 * @param filePath
	 * @param ispass
	 * @param countAccuracy
	 * @param bufferedwrite
	 * @return
	 */
	public static Integer orderDataToDestFile(Integer[] arr, boolean ispass, int countAccuracy,BufferedWriter bufferedwrite) {
		Integer temp = 0; // 记录最后一个值
		//int tempCount = 0; // 记录写入的数据位置,下标值

		try {
			Integer object = arr[0];
			/*for (Integer obj : arr) {
				Integer object = obj;

				// 判断是否是最后一个数
				if (tempCount == arr.length - 1) {
					// 判断是否还有数
					if (arr.length <= countAccuracy && ispass) {
						temp = null;
					} else {
						temp = object;
						break;
					}
				}

				// 写入目标排序总文件
				bufferedwrite.write(object + "\r\n");

				// 记录数据的下标
				tempCount++;
			}*/
			if(object != null)
				temp = object;
			bufferedwrite.write(object + "\r\n");
		} catch (IOException e) {
			e.printStackTrace();
		}
		return temp;
	}
}
